The present invention relates generally to a scheme for communications within a computer network and, in particular, to such communications as occur between nodes in such a network across a wireless link.
Modern computer networks allow for inter-communication between a number of nodes such as personal computers, workstations, peripheral units and the like. Network links transport information between these nodes, which may sometimes be separated by large distances. However, to date most computer networks have relied on wired links to transport this information. Where wireless links are used, they have typically been components of a very large network, such as a wide area network, which may employ satellite communication links to interconnect network nodes separated by very large distances. In such cases, the transmission protocols used across the wireless links have generally been established by the service entities carrying the data being transmitted, for example, telephone companies and other service providers.
In the home environment, computers have traditionally been used as stand-alone devices. More recently, however, there have been some steps taken to integrate the home computer with other appliances. For example, in so-called xe2x80x9cSmart Homesxe2x80x9d, computers may be used to turn on and off various appliances and to control their operational settings. In such systems, wired communication links are used to interconnect the computer to the appliances that it will control. Such wired links are expensive to install, especially where they are added after the original construction of the home.
In an effort to reduce the difficulties and costs associated with wired communication links, some systems for interconnecting computers with appliances have utilized analog wireless links for transporting information between these units. Such analog wireless links operate at frequencies commonly utilized by wireless telephones. Although easier to install than conventional wired communication links, analog wireless communication links suffer from a number of disadvantages. For example, degraded signals may be expected on such links because of multipath interference. Further, interference from existing appliances, such as televisions, cellular telephones, wireless telephones and the like, may be experienced. Thus, analog wireless communication links offer less than optimum performance for a home environment.
In a co-pending application, Ser. No. 09/151,579, which is assigned to the assignee of the present application and is incorporated herein by reference, a computer network employing a digital wireless communication link adapted for use in the home and other environments was described. The architecture of that network (referred to in the previously cited provisional application as a xe2x80x9cWhitecapxe2x80x9d network) included a number of network components arranged in a hierarchical fashion and communicatively coupled to one another through communication links operative at different levels of the hierarchy. At the highest level of the hierarchy, a communication protocol that supports dynamic addition of new network components at any level of the hierarchy according to bandwidth requirements within a communication channel operative at the highest level of the network hierarchy is used.
The generalization of this network structure is shown in FIG. 1. A subnet 10 includes a server 12. In this scheme, the term xe2x80x9csubnetxe2x80x9d is used to describe a cluster of network components that includes a server and several clients associated therewith (e.g., coupled through the wireless communication link). Depending on the context of the discussion however, a subnet may also refer to a network that includes a client and one or more subclients associated therewith. A xe2x80x9cclientxe2x80x9d is a network node linked to the server through the wireless communication link. Examples of clients include audio/video equipment such as televisions, stereo components, personal computers, satellite television receivers, cable television distribution nodes, and other household appliances.
Server 12 may be a separate computer that controls the communication link, however, in other cases server 12 may be embodied as an add-on card or other component attached to a host computer (e.g., a personal computer) 13. Server 12 has an associated radio 14, which is used to couple server 12 wirelessly to the other nodes of subnet 10. The wireless link generally supports both high and low bandwidth data channels and a command channel. Here a channel is defined as the combination of a transmission frequency (more properly a transmission frequency band) and a pseudo-random (PN) code used in a spread spectrum communication scheme. In general, a number of available frequencies and PN codes may provide a number of available channels within subnet 10. As is described in the co-pending application cited above, servers and clients are capable of searching through the available channels to find a desirable channel over which to communicate with one another.
Also included in subnet 10 are a number of clients 16, some of which have shadow clients 18 associated therewith. A shadow client 18 is defined as a client which receives the same data input as its associated client 16 (either from server 12 or another client 16), but which exchanges commands with server 12 independently of its associated client 16. Each client 16 has an associated radio 14, which is used to communicate with server 12, and some clients 16 may have associated subclients 20. Subclients 20 may include keyboards, joysticks, remote control devices, multi-dimensional input devices, cursor control devices, display units and/or other input and/or output devices associated with a particular client 16. A client 16 and its associated subclients 20 may communicate with one another via communication links 21, which may be wireless (e.g., infra-red, ultrasonic, spread spectrum, etc.) communication links.
Each subnet 10 is arranged in a hierarchical fashion with various levels of the hierarchy corresponding to levels at which intra-network component communication occurs. At a highest level of the hierarchy exists the server 12 (and/or its associated host 13), which communicates with various clients 16 via the wireless radio channel. At other, lower levels of the hierarchy the clients 16 communicate with their various subclients 20 using communication links 21, for example, wired communication links or wireless communication links such as infrared links.
Where half-duplex radio communication is used on the wireless link between server 12 and clients 16, a communication protocol based on a slotted link structure with dynamic slot assignment is employed. Such a structure supports point-to-point connections within subnet 10 and slot sizes may be re-negotiated within a session. Thus a data link layer that supports the wireless communication can accommodate data packet handling, time management for packet transmission and slot synchronization, error correction coding (ECC), channel parameter measurement and channel switching. A higher level transport layer provides all necessary connection related services, policing for bandwidth utilization, low bandwidth data handling, data broadcast and, optionally, data encryption. The transport layer also allocates bandwidth to each client 16, continuously polices any under or over utilization of that bandwidth, and also accommodates any bandwidth renegotiations, as may be required whenever a new client 16 comes on-line or when one of the clients 16 (or an associated subclient 20) requires greater bandwidth.
The slotted link structure of the wireless communication protocol for the transmission of real time, multimedia data (e.g., as frames) within a subnet 10 is shown in FIG. 2. At the highest level within a channel, forward (F) and backward or reverse (B) slots of fixed (but negotiable) time duration are provided within each frame transmission period. During forward time slots F, server 12 may transmit video and/or audio data and/or commands to clients 16, which are placed in a listening mode. During reverse time slots B, server 12 listens to transmissions from the clients 16. Such transmissions may include audio, video or other data and/or commands from a client 16 or an associated subclient 20. At the second level of the hierarchy, each transmission slot (forward or reverse) is made up of one or more radio data frames 40 of variable length. Finally, at the lowest level of the hierarchy, each radio data frame 40 is comprised of server/client data packets 42, which may be of variable length.
Each radio data frame 40 is made up of one server/client data packet 42 and its associated error correction coding (ECC) bits. Variable length framing is preferred over constant length framing in order to allow smaller frame lengths during severe channel conditions and vice-versa. This adds to channel robustness and bandwidth savings. Although variable length frames may be used, however, the ECC block lengths are preferably fixed. Hence, whenever the data packet length is less than the ECC block length, the ECC block may be truncated (e.g., using conventional virtual zero techniques). Similar procedures may be adopted for the last block of ECC bits when the data packet is larger.
As shown in the illustration, each radio, data frame 40 includes a preamble 44, which is used to synchronize pseudo-random (PN) generators of the transmitter and the receiver. Link ID 46 is a field of fixed length (e.g., 16 bits long for one embodiment), and is unique to the link, thus identifying a particular subnet 10. Data from the server 12/client 16 is of variable length as indicated by a length field 48. Cyclic redundancy check (CRC) bits 50 may be used for error detection/correction in the conventional fashion.
For the illustrated embodiment then, each frame 52 is divided into a forward slot F, a backward slot B, a quiet slot Q and a number of radio turn around slots T. Slot F is meant for server 12-to-clients 16 communication. Slot B is time shared among a number of minislots B1, B2, etc., which are assigned by server 12 to the individual clients 16 for their respective transmissions to the server 12. Each mini-slot B1, B2, etc. includes a time for transmitting audio, video, voice, lossy data (i.e., data that may be encoded/decoded using lossy techniques or that can tolerate the loss of some packets during transmission/reception), lossless data (i.e., data that is encoded/decoded using lossless techniques or that cannot tolerate the loss of any packets during transmission/reception), low bandwidth data and/or command (Cmd.) packets. Slot Q is left quiet so that a new client may insert a request packet when the new client seeks to login to the subnet 10. Slots T appear between any change from transmit to receive and vice-versa, and are meant to accommodate individual radios"" turn around time (i.e., the time when a half-duplex radio 14 switches from transmit to receive operation or vice-versa). The time duration of each of these slots and mini-slots may be dynamically altered through renegotiations between the server 12 and the clients 16 so as to achieve the best possible bandwidth utilization for the channel. Note that where full duplex radios are employed, each directional slot (i.e., F and B) may be full-time in one direction, with no radio turn around slots required.
Forward and backward bandwidth allocation depends on the data handled by the clients 16. If a client 16 is a video consumer, for example a television, then a large forward bandwidth is allocated for that client. Similarly if a client 16 is a video generator, for example a video camcorder, then a large reverse bandwidth is allocated to that particular client. The server 12 maintains a dynamic table (e.g., in memory at server 12 or host 13), which includes forward and backward bandwidth requirements of all on-line clients 16. This information may be used when determining whether a new connection may be granted to a new client. For example, if a new client 16 requires more than the available bandwidth in either direction, server 12 may reject the connection request. The bandwidth requirement (or allocation) information may also be used in deciding how many radio packets a particular client 16 needs to wait before starting to transmit its packets to the server 12. Additionally, whenever the channel conditions change, it is possible to increase/reduce the number of ECC bits to cope with the new channel conditions. Hence, depending on whether the information rate at the source is altered, it may require a dynamic change to the forward and backward bandwidth allocation.
Within any computer network environment, and particularly within wireless networks, packets that are transmitted by one node may be lost before being properly received by the intended receiving node. The reasons for such losses may vary from one network to another, but in general may be due to the use of lossy communications protocols, lossy transmission mediums, interference from other transmission sources, overflows at the receiving node, or other reasons. Thus, a retransmission scheme is needed to allow for retransmissions of data that may have been lost sometime after being transmitted by the transmitting node.
In one embodiment, data is transmitted over a computer network from a source network component to one or more destination network components. Thereafter, one or more acknowledgements are transmitted from one of the destination network components to the source network component; and different data from the previously transmitted data is transmitted from the source network component to the one or more destination network components upon a failure to receive said one or more acknowledgements from said one of the destination network component. The previously transmitted data may be retransmitted from the source network component to one or more destination network components upon a failure to receive said one or more acknowledgements from said destination network component and upon expiration of a specified timeout period.
Further, network frames may be transmitted over a computer network from a source network component to one or more destination network components, the frames including one or more sequentially identified packets of data. A negative acknowledgement message from a destination network component may be transmitted to the source network component upon a failure to receive one or more of the transmitted data packets, the acknowledgment including packet identifications of said one or more data packets. Then data packets identified by the identifications received in a negative acknowledgement may be retransmitted before transmitting other packets. The negative acknowledgements thus indicate failed receipt of data. Positive acknowledgements indicate successful receipt of data.
In some embodiments, a portion of bandwidth may be reserved through negotiations between source and destination network components for each data stream transmitted. Data may be transmitted as sequentially identified packets within a network frame and the number of packets transmitted within a network frame may be dynamically negotiated for each data stream transmitted between two network components. Any acknowledgements may include the packet identifications of such data packets.
In some embodiments the source network component maintains an index of sequential packets available for retransmission. The retransmission index dynamically spans from the last non-acknowledged packet to the last transmitted packet in the sequence.
In some embodiments the number of times a packet is retransmitted before being dropped it is dynamically negotiated for each stream of data transmitted between two or more network components. Any packets with identifications included in a negative acknowledgement are preferably retransmitted at least once before transmitting any other packets within a network frame.
A further embodiment provides an interface communicatively coupling a system with a computer network. The interface includes means for transmitting data over a computer network from a source network component to one or more destination network components; means for transmitting one or more acknowledgements from a destination network component to the source network component; and means for transmitting different data from the previously transmitted data from the source network component to one or more destination network components upon failure to receive said one or more acknowledgements from said destination network component.
A further embodiment provides a system communicatively coupled with a computer network. The system may include means for transmitting data over a computer network from a source network component to one or more destination network components; means for transmitting one or more acknowledgements from a destination network component to the source network component; and means for transmitting different data from the previously transmitted data from the source network component to one or more destination network components upon failure to receive said one or more acknowledgements from said destination network component.
In still further embodiments, a modulated signal embodying one or more computer-readable symbols, which when organized in a computer platform, allow said platform to acknowledge reception of stream data in accordance therewith. Such symbols contain one or more of the following fields: a packet type, a stream ID, the length of acknowledgement message, a beginning sequence number, an ending sequence number, and the status of each packet between the beginning sequence number and the ending sequence number. In other cases, such symbols might contain one or more of the following: a packet type, a stream ID, and a packet sequence number; or a packet type, a stream ID, and a starting packet sequence number.
These and other features and advantages of the present invention will be apparent from a review of the detailed description and its accompanying drawings that follow.